Search Results

Documents authored by Eriguchi, Reo

Document
DOI: 10.4230/LIPIcs.ITC.2022.1
Multi-Server PIR with Full Error Detection and Limited Error Correction

Authors: Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

Abstract
An 𝓁-server Private Information Retrieval (PIR) scheme allows a client to retrieve the τ-th element a_τ from a database a = (a₁,…,a_n) which is replicated among 𝓁 servers. It is called t-private if any coalition of t servers learns no information on τ, and b-error correcting if a client can correctly compute a_τ from 𝓁 answers containing b errors. This paper concerns the following problems: Is there a t-private 𝓁-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1-ε even if 𝓁-1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1-ε)-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most t queries, which reflects t-privacy. We then prove an impossibility result that there exists no 1-fully error detecting (i.e., ε = 0) PIR scheme with o(n) communication. Next, for ε > 0, we construct 1-private (1-ε)-fully error detecting and (𝓁/2-O(1))-error correcting PIR schemes which have n^{o(1)} communication, and a t-private one which has O(n^{c}) communication for any t ≥ 2 and some constant c < 1. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability.
Cite as

Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida. Multi-Server PIR with Full Error Detection and Limited Error Correction. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.ITC.2022.1,
  author =	{Eriguchi, Reo and Kurosawa, Kaoru and Nuida, Koji},
  title =	{{Multi-Server PIR with Full Error Detection and Limited Error Correction}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.1},
  URN =		{urn:nbn:de:0030-drops-164796},
  doi =		{10.4230/LIPIcs.ITC.2022.1},
  annote =	{Keywords: Private Information Retrieval, Error Detection, Error Correction}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.2
d-Multiplicative Secret Sharing for Multipartite Adversary Structures

Authors: Reo Eriguchi and Noboru Kunihiro

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.
Cite as

Reo Eriguchi and Noboru Kunihiro. d-Multiplicative Secret Sharing for Multipartite Adversary Structures. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eriguchi_et_al:LIPIcs.ITC.2020.2,
  author =	{Eriguchi, Reo and Kunihiro, Noboru},
  title =	{{d-Multiplicative Secret Sharing for Multipartite Adversary Structures}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.2},
  URN =		{urn:nbn:de:0030-drops-121079},
  doi =		{10.4230/LIPIcs.ITC.2020.2},
  annote =	{Keywords: Secret sharing scheme, multiplicative secret sharing scheme, multipartite adversary structure}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact